package com.bupt.chapter.third.two_dis_find;

public class Solution {
	public static void main(String[] args) {
		int[] nums = { 1, 2, 3, 3, 3, 4, 5, 6, 7, 7, 7 };
		System.out.println(Solution.biSearch(nums, 6));
	}

	public static int biSearch(int[] nums, int target) {
		return biSearch(nums, target, 0, nums.length);
	}

	public static int biSearch(int[] nums, int target, int start, int end) {
		if (start <= end) {
			int half = start + (end - start) / 2;
			if (nums[half] == target) {
				if (half + 1 < nums.length && nums[half + 1] == target)
					return biSearch(nums, target, half + 1, end);
				else {
					return half;
				}
			} else if (nums[half] < target) {
				return biSearch(nums, target, half + 1, end);
			} else {
				return biSearch(nums, target, start, half - 1);
			}
		}
		return -1;
	}
}
